package com.dbh.alg.algorithm.quest;

import java.util.LinkedList;
import java.util.List;

/**
 * 有100个囚犯围成一圈，编号从1到100。每隔一个囚犯就枪毙一个，直到只剩下最后一个囚犯。请编写一个程序，找出最后存活的囚犯的编号。
 */
public class LastPrisonerStanding {

    public static void main(String[] args) {
        int n = 100;
        System.out.println("最后存活的囚犯编号是:" + findLastPerson(n));
    }

    public static int findLastPerson(int n) {
        List<Integer> prisoners = new LinkedList<>();

        // 初始化囚犯编号
        for (int i = 1; i <= n; i++) {
            prisoners.add(i);
        }

        // 模拟枪毙
        while (prisoners.size() > 1) {
            List<Integer> survivors = new LinkedList<>();

            // 只保留偶数位置的囚犯
            for (int i = 1; i < prisoners.size(); i += 2) {
                survivors.add(prisoners.get(i));
            }

            prisoners = survivors;
        }

        // 返回最后存活的囚犯编号
        return prisoners.get(0);
    }
}
